Дана 2д карта, на которой есть стартовая и конечная точка, а также многоугольники, которые нельзя пересекать. Рассмотрим след. алгоритм: принимаем все вершины многоугольников, стартовую и конечную точку как точки графа. Строим всевозможные пути, которые не пересекают ни один из полигонов. Получаем взвешенный граф, где длины рёбер это реальные геометрические длины этих отрезков. Начиная с начальной точки, смотрим все линии, которые ведут к соседней вершине и из этих соседних вершин проводим прямой путь (теперь уже не обращая внимания на препятствия) до конечной точки. Например, у нас есть прямой путь из начальной точки в пункт A и в пункт B, начальная точка пускай будет O. Тогда, согласно алгоритму, нужно сравнить суммы
[math]OA + A->F, OB + B->F[/math] (F - конеч. точка, -> означает прямой отрезок от одной точки к другой без учёта пересечения с многоугольниками). Смотрим, какая из сумм меньше, выбираем соответствующий путь. Допустим, выбрали B. Тогда делаем то же самое, только теперь начиная с точки B. Делаем так, пока не дойдём до F.
Теперь вопрос: всегда ли этот алгоритм будет приводить нас к кратчайшему пути в графе? Если ответ утвердительный, прошу привести доказательство, если отрицательный - хотя бы один пример, когда алгоритм ломается. Спасибо всем, кто обратит внимание на вопрос.
