|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
05.06.2012, 20:54 | #1 |
Новичок
Джуниор
Регистрация: 05.06.2012
Сообщений: 2
|
Нахождение кратчайшего пути
Доброго времени суток форумчане. У меня возникла проблема с решением задачи в екселе о нахождении кратчайшего пути. Мне дали 2 скрина и сказали делать по ним, но я не могу разобраться что к чему ибо не сталкивался с этим ни разу. Буду признателен если кто нибудь объяснит мне что да как. Всем добра
|
05.06.2012, 22:38 | #3 |
Новичок
СтарожилДжуниор
Регистрация: 05.02.2008
Сообщений: 9,487
|
Сережа, спасибо!
уж отпиарил, так отпиарил продолжим. без макросов. настроение сегодня преотличное. надеюсь не промахнулся... проверяйте
Программисты - это люди, решающие проблемы, о существовании которых Вы не подозревали, методами, которых Вы не понимаете
|
05.06.2012, 23:12 | #4 |
Новичок
Джуниор
Регистрация: 05.06.2012
Сообщений: 2
|
спасибо Игорь. Завтра покажу и узнаю подойдет ли такое решение или же нужно как в примере который мне дали.
|
05.06.2012, 23:15 | #5 |
Пользователь
Регистрация: 18.03.2012
Сообщений: 68
|
Игорь , для чаиников , как работает ваш фаил ?
|
06.06.2012, 01:34 | #6 |
Новичок
СтарожилДжуниор
Регистрация: 05.02.2008
Сообщений: 9,487
|
Сережа (eikhner), не надо прибедняться. Как минимум ты кофейник, а не чайник.
понимать как это сработало в екселе гораздо проще если понимать, как это работает в математике. обьяснять в деталях будет дольше, чем я формулы писал. есть еще одна проблема - необхоимо смотреть одновременно на граф, на таблицу с данными и читать вот это, а глазьев всего два штуки. начнем с подгоовки данных. введем обозначения: мХ - самый короткий маршрут от 1 до т.Х пХ!У - расстояние (путь) от т.Х до т,У. расстояния между точкам в файле указаны так - начальная точка соотв. №строки, конечная - №столбца. например из т.3 можо попасть в 4 и 7, путь п3!4 = 5 и п3!7 = 6. соотв. числа 5 и 6 записаны в 4-й и 7-й колоках 3-й строки. Из 7 можно попасть в 8 и 10, пути п7!8 = 2 и п7!10 = 2, соотв. 2 и 2 должны были быть написаны в 8-ю и 10-ю колонки 7-й строки. в файле ошибка, в 8-й колонке 7-й строки пусто, а должно было бы быть 2. в т.10 можно попасть из 7,8,9. допустим нам известны самые короткие маршруты до этих точек м7,м8,м9. минимальным маршрутом до 10 будет мин(м7+п7!10;м8+п8!10;м9+п9!10). смотрим, вторая таблица, в т.4 можно попасть через 2 и 3 соотв п1!2!4 = 6, п1!3!4 = 8. и т.д. и последнее, как построен сам маршрут. нашли в 10-й колонке самое маленькое число = 9 - это есть самый короткий маршрут. нашли в какой строке находится это число (оказалось тоже в строке 9,совпадение). т.е в 10-ю точку пришли из 9-й. находим самое маленькое число в 9-й колонке, это число 8 (оно вообще одно в 9-й колонке), находим в какой строке оно находится - в 5-й. значит в 9-ю пришли с 5-й точки, смотрим на граф а по другому и не может быть. и т.д. пора спать.
Программисты - это люди, решающие проблемы, о существовании которых Вы не подозревали, методами, которых Вы не понимаете
Последний раз редактировалось IgorGO; 16.06.2012 в 22:06. |
06.06.2012, 08:46 | #7 |
Пользователь
Регистрация: 18.03.2012
Сообщений: 68
|
Игорь, спасибо .
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Поиск кратчайшего пути в графе | BaceK | Помощь студентам | 0 | 18.12.2011 11:49 |
Нахождение кратчайшего пути в графе | Nata220 | Помощь студентам | 4 | 29.11.2010 14:54 |
поиск кратчайшего пути | LENA_M | Общие вопросы C/C++ | 0 | 29.05.2010 22:15 |
Алгоритм Беллмана-форда,нахождение кратчайшего пути | bakir | Помощь студентам | 1 | 13.01.2010 02:31 |