|
|
ru.algorithms- RU.ALGORITHMS ---------------------------------------------------------------- From : Vitaly Slobodskoy 2:5015/128.22 03 May 2002 21:48:53 To : Arthur Martirosyan Subject : Re: Дейкстра -------------------------------------------------------------------------------- До меня докатились слухи, что ты что-то там написал о "Дейкстра"! Так, так... надо бы разобраться... 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>> Вот, как бы и все! Так в чем проблема??? AM> ОК! походу я немного прогнал, вернее делал не так.. все же пара вопросов AM> осталась, а именно: почему у нас сразу отпадает 4-я вершина, путь дальше AM> через нее не рассматривается, тогда, как 5-ю вершину мы рассматриваем до AM> конца и получаем таки через нее кратчайший путь, чем это определяется? по AM> логике все понятно, но как это обьяснять машине.. Значит ты не уловил алгоритм. Рекомендую еще раз почитать мое письмо, в котором я довольно подробно рассказал об алгоритме. Hа каждом новом шаге (создавая новый столбец таблицы), мы выбираем из всех строк минимальное значение (на первом шаге это 2 у 2-ого пункта, на 2-ом шаге это 4 у 3-его пункта, на 3-ем шаге это 4 у 4-ого пункта и т.д.). Ту строку, в которой нашли, дальше не рассматриваем, это означает, что до пункта, соответствующего этой строке, кратчайший путь найден, далее для этого пункта рассматривать нет смысла - вычеркиваем ее (мысленно) и ставим эту новую вершину в заголовок нового столбца. Как формируется новый столбец, я уже рассказывал. Все строго по алгоритму - машине нужно только выбрать минимум и строить на новом шаге новый столбец!! Hадеюсь, что теперь понятно. Пока, Arthur.. Vitaly Slobodskoy FIDO: 2:5015/128.22 E-Mail: vital@mail.nnov.ru --- WP/95 Rel 1.78E (215.0) Reg. * Origin: ЭТО вам не ЭТО! Понятно! (ДМБ) (2:5015/128.22) Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
Архивное /ru.algorithms/39086c104b87.html, оценка из 5, голосов 10
|