| | | | |
Определение кратчайшего пути между двумя точками | Полный текст материала
Другие публикации автора: Вадим Кегелес
Цитата или краткий комментарий: «... Существует несколько методов для решения этой задачи (метод Флойда, алгоритм Дейкстры и др.) Но описания этих методов мне показались сложными (и для меня - не математика - не совсем понятными), по-этому хотелось найти, что-нибудь более простое.
...» |
Важно:- Страница предназначена для обсуждения материала, его содержания, полезности, соответствия действительности и так далее. Смысл не в разборке, а в приближении к истине :о) и пользе для всех.
- Любые другие сообщения или вопросы, а так же личные эмоции в адрес авторов и полемика, не относящаяся к теме обсуждаемого материала, будут удаляться без предупреждения авторов, дабы не мешать жителям нормально общаться.
- При голосовании учитывайте уровень, на который расчитан материал. "Интересность и полезность" имеет смысл оценивать относительно того, кому именно предназначался материал.
- Размер одного сообщений не должен превышать 5К. Если Вам нужно сказать больше, сделайте это за два раза. Или, что в данной ситуации правильнее, напишите свою статью.
Всегда легче осудить сделанное, нежели сделать самому. Поэтому, пожалуйста, соблюдайте правила Королевства и уважайте друг друга.
Добавить свое мнение.
| | Содержит полезные и(или) интересные сведения | [1] | 7 | 50% | | | | Ничего особенно нового и интересного | [2] | 7 | 50% | | | | Написано неверно (обязательно укажите почему) | [3] | 0 | 0% | | Всего проголосовали: 14 | | | Все понятно, материал читается легко | [1] | 10 | 90.9% | | | | Есть неясности в изложении | [2] | 1 | 9.1% | | | | Непонятно написано, трудно читается | [3] | 0 | 0% | | Всего проголосовали: 11 |
[Задачи оптимизации] [Программирование игр.]
Отслеживать это обсуждение
Всего сообщений: 1604-01-2011 18:05Для GEO
Я дал конструктивную критику, но не здесь, а в своей статье на эту тему. Претензия у меня, по большому счету, одна единственная — неэффективная реализация: Вы на каждом шаге пробегаете по всем элементам массива. Это прокатит на относительно небольших массивах, но приведет к жутким тормозам, если размеры массива вырастут.
Это так, но только для случая когда надо кратчайшим путем провести маршрут из одной точки в другую. Ваш варант я читал.
На самом деле, если нужно решать, например, задачу эвакуации множества людей из помещения через некоторый выход, то предварительно рассчитав карту маршрута от выхода во все точки помещения и сохранив ее, вы получите все маршруты всех эвакуируемых, как бы вы их в дальнейшем не расставляли :). А если надо учитывать еще и изменение стоимости прохождения по клеткам от количества занятых соседних (плотность толпы), то такой подход, то что надо для ачала разработки своего решения :) |
|
30-10-2009 13:15Ой, забыл ответить еще на вот это
>>> В конце концов статью можно изъять
Если статья опубликована, значит она прошла согласование в Команде Королевства. Администрация не возражает против ее размещения, значит, видит в ней полезность. Так зачем же ее изымать? ;-) |
|
30-10-2009 13:08>>> И не видит, к сожалению, конструктивной критики
Увы, раздражающим фактором послужило Ваше присвоение собственного имени давно и хорошо известному (и достаточно простому и очевидному) алгоритму. Поэтому все вертится вокруг этого.
Я дал конструктивную критику, но не здесь, а в своей статье на эту тему. Претензия у меня, по большому счету, одна единственная -- неэффективная реализация: Вы на каждом шаге пробегаете по всем элементам массива. Это прокатит на относительно небольших массивах, но приведет к жутким тормозам, если размеры массива вырастут.
А в целом, все нормально. Вы предложили простую и понятную реализацию для простого случая. Хороший пример для новичков. Если попридираться, то немного подача хромает (или композация): текст программы доминирует, а было бы лучше разбавлять его описанием алгоритма на русском языке. Но в целом, это мелочь. Мы же на программистском форуме, а не на факультете журналистики ;-) |
|
30-10-2009 12:47>>> Geo, помему, вы только и делаете, что иронизируете
Мухтар, а Вы только и делаете, что выказываете недовольство моими действиями?
Вам нужны пояснения по моему предыдущему сообщению, или Вы просто пар выпускали? |
|
30-10-2009 08:04сообщение от автора материала Спасибо, Мухтар. Да автор сюда заглядывает. И не видит, к сожалению, конструктивной критики. Наверное, не скромно обозвать известный метод своим именем (но как-то же его назвать надо было, хотя бы для идентификации). Ну называйте это
"частным случаем алгоритма Дейкстры"
или "всем известный случай волнового алгоритма" - суть-то не в этом. Я не знал о волновом алгоритме, на олимпиадах по программированию не участвовал и программировать начал сам (без специального образования, если не считать 4-х месячных курсов).
Только не могу понять, что плохого в том, что я описал (на мой взгляд просто и доступно) один из способов решения подобной задачи (пусть и ранее известный).
Да большинство решений описанных в Сокровищнице или в Подземелье Магов на момент их написания были уже кому-то известны. Но тем не менее, я лично благодарен всем авторам , за то что они не поленились и разжевали для меня какую-то задачу, которую, может быть
"любой олимпиадник по программированию"
и так знает.
Кстати, я благодарен так же и Geo, за то что он помогал мне в вопросах на Круглом столе.
Но я не настаиваю на своем мнении. В конце концов статью можно изъять. Но я удовлетворен, что хотя бы двоим (судя по оценкам) моя статья помогла (видимо они тоже не участвовали в олимпиадах по программированию). |
|
30-10-2009 06:16Geo, помему, вы только и делаете, что иронизируете.
Интересно, автор сюда вообще заглядывает? |
|
28-10-2009 11:41Виктор, Вы бы хоть смайлики ставили что ли. А то, знаете ли, далеко не все посетители в состоянии уловить Вашу тонкую иронию ;-) |
|
28-10-2009 09:13Материал, изложенный в статье обладает наивысшей полезностью, так как предельно элементарным способом отвечает на базовый вопрос любой задачи - как кратчайшим образом достичь цели, обходя неизбежные препятствия.
Это открытие - один из самых замечательных способов приближения к истине, когда-либо алгоритмизированных, если вообще не единственный.
Внедрение алгоритма Кегелеса-Рауера в другие задачи может
повлечь за собой неожиданные решения, кроме того благодаря этому, теперь становится доступной оптимизация любых процессов, поддающихся дигитализации, что, в конечном счете, означает решение практически любых проблем с минимальными затратами.
|
|
07-07-2003 11:49Genial'no... Ugh skol'ko raz tverdili miru... Togda ugh luchshe nazvat' algoritm moim imenem, ya do nego na olimpiade v 95-m godu doshel... Infy - minimum, pretenzii - maksimum! |
|
07-07-2003 11:11Вобщем то ничё нового конеш в статье нет, но в принципе если человек сам изучил какой нить язык или просто только начинает статья для него наверное будет полезной. Так что не пинайте автора а лучше сами выложите исходники с курса теории графов |
|
03-07-2003 12:26Не надо клевать людей. Ну, поторопились, назвали модификации волнового алгоритма своим именем, так ведь это заслуженная гордость. То, что они "изобрели" является достаточно эффективным алгоритмом. Но с другой стороны, время, которое было потрачено на разработку, можно было бы потратить на изучение математики, дискретной в частности.
Вспоминается одна байка.
Во времена Чебышева, один сапожник был не типичен для своей профессии, нравилось ему развлекаться с цифрами. Годам к сорока, этот пролетарий обобщил все, до чего он додумался и пошел хвастаться в университет перед профессорами. А эти, буржуазные выкормыши, сказали, что все представленное, давно известно и называется основами дифференциального исчисления. Для сапожника жизнь потеряла смысл, и он повесился.
|
|
03-07-2003 11:25Вы считаете, что алгоритм Дейкстры сложный ? :))
тогда Вы еще не видели сложных алгоритмов :) |
|
03-07-2003 08:45Этот алгоритм знает (должен знать) любой олимпиадник по программированию. Хотя то, что вы сами "дошли" до него - вызывает уважение. |
|
03-07-2003 07:23
02-07-2003 22:56институт вспомнился. на первом курсе тоже "изобрел" аналогичный метод. правда, пользовался рекурсией, но принцип тот же. |
|
02-07-2003 21:18Это т.н. "Волновой алгоритм". В Ru.Algorithm им тыкают в лицо каждому, кто задает соответсвующий вопрос. В общем, это не новость :)
По большому счету, это частный случай алгоритма Дейкстры.
Ну а реализация, как верно заметил сам автор,-- далека от совершенства.
|
|
|
|