|
|
ru.algorithms- RU.ALGORITHMS ---------------------------------------------------------------- From : Arthur Martirosyan 2:5061/103.51 01 May 2002 15:34:48 To : Vitaly Slobodskoy Subject : Дейкстра -------------------------------------------------------------------------------- Четверг Май 02 2002 21:43 You wrote: AM>> | 1 2 3 4 5 6 7 AM>> -|-+--+--+--+--+--+--+--+--+--- AM>> 1| oo 2 5 4 oo oo oo | AM>> 2| 2 oo 2 oo 7 oo oo | AM>> 3| 5 2 oo 1 4 3 oo | AM>> 4| 4 oo 1 oo oo 4 oo | AM>> 5| oo 7 4 oo oo 5 5 | AM>> 6| oo oo 3 4 5 oo 7 | AM>> 7| oo oo oo oo 5 7 oo | AM>> Это простой пример, который я просто еру за основу.. Опять же, AM>> встречаются и вообще тупиковые ситуации, когда придется двигаться AM>> обратно.. VS> Пож-ста, вот решение этой задачи тем алгоритмом, который я приводил: VS> 1 | 2 | 3 | 4 | 6 | VS> -+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+- VS> 2 | 2* |-+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--- VS> 3 | 5 | 4(1-2)* |-+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-- VS> 4 | 4 | 4(1) | 4(1)* |-+--+--+--+--+--+--+--+--+--+--+--+--- VS> 5 | oo | 9(1-2) | 8(1-2-3) | 8(1-2-3) | 8(1-2-3)* |-+--+--+--+- VS> 6 | oo | oo | 7(1-2-3) | 7(1-2-3)* |-+--+--+--+--+--+--+--+--- VS> 7 | oo | oo | oo | oo | 14(1-2-3-6) | 13(1-2-3-5) VS> В скобках указана история. В принципе, это не предусматривается VS> алгоритмом, т.к. его задача - это - минимальное расстояние, но, VS> согласись, хранить ее не сложно. Итак, мы имеем такие кратчайшие пути VS> из пункта 1 во все остальные: в пункт 2: 1->2 (длина 2) в пункт 3: 1->2->> 3 (длина 4) в пункт 4: 1->4 (длина 4) в пункт 5: 1->2->3->5 VS> (длина 8) в пункт 6: 1->2->3->6 (длина 7) в пункт 7: 1->2->3->5->7 VS> (длина 13) VS> Вот, как бы и все! Так в чем проблема??? ОК! походу я немного прогнал, вернее делал не так.. все же пара вопросов осталась, а именно: почему у нас сразу отпадает 4-я вершина, путь дальше через нее не рассматривается, тогда, как 5-ю вершину мы рассматриваем до конца и получаем таки через нее кратчайший путь, чем это определяется? по логике все понятно, но как это обьяснять машине.. ... OK!____________________________________________________________________ --- Желаю удачи и всего хорошего, Arthur M. ------------------------------- * Origin: A dream comes true (2:5061/103.51 Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
Архивное /ru.algorithms/239273cd00cac.html, оценка из 5, голосов 10
|