Rambler's Top100
"Knowledge itself is power"
F.Bacon
Поиск | Карта сайта | Помощь | О проекте | ТТХ  
 Подземелье Магов
  
 

Фильтр по датам

 
 К н и г и
 
Книжная полка
 
 
Библиотека
 
  
  
 


Поиск
 
Поиск по КС
Поиск в статьях
Яndex© + Google©
Поиск книг

 
  
Тематический каталог
Все манускрипты

 
  
Карта VCL
ОШИБКИ
Сообщения системы

 
Форумы
 
Круглый стол
Новые вопросы

 
  
Базарная площадь
Городская площадь

 
   
С Л С

 
Летопись
 
Королевские Хроники
Рыцарский Зал
Глас народа!

 
  
ТТХ
Конкурсы
Королевская клюква

 
Разделы
 
Hello, World!
Лицей

Квинтана

 
  
Сокровищница
Подземелье Магов
Подводные камни
Свитки

 
  
Школа ОБЕРОНА

 
  
Арсенальная башня
Фолианты
Полигон

 
  
Книга Песка
Дальние земли

 
  
АРХИВЫ

 
 

Сейчас на сайте присутствуют:
 
  
 
Во Флориде и в Королевстве сейчас  04:24[Войти] | [Зарегистрироваться]

Обсуждение материала
Определение кратчайшего пути между двумя точками
Полный текст материала


Другие публикации автора: Вадим Кегелес

Цитата или краткий комментарий:

«... Существует несколько методов для решения этой задачи (метод Флойда, алгоритм Дейкстры и др.) Но описания этих методов мне показались сложными (и для меня - не математика - не совсем понятными), по-этому хотелось найти, что-нибудь более простое. ...»


Важно:
  • Страница предназначена для обсуждения материала, его содержания, полезности, соответствия действительности и так далее. Смысл не в разборке, а в приближении к истине :о) и пользе для всех.
  • Любые другие сообщения или вопросы, а так же личные эмоции в адрес авторов и полемика, не относящаяся к теме обсуждаемого материала, будут удаляться без предупреждения авторов, дабы не мешать жителям нормально общаться.
  • При голосовании учитывайте уровень, на который расчитан материал. "Интересность и полезность" имеет смысл оценивать относительно того, кому именно предназначался материал.
  • Размер одного сообщений не должен превышать 5К. Если Вам нужно сказать больше, сделайте это за два раза. Или, что в данной ситуации правильнее, напишите свою статью.
Всегда легче осудить сделанное, нежели сделать самому. Поэтому, пожалуйста, соблюдайте правила Королевства и уважайте друг друга.



Добавить свое мнение.

Результаты голосования
Оценка содержания

  Содержит полезные и(или) интересные сведения
[1]750%
 
  Ничего особенно нового и интересного
[2]750%
 
  Написано неверно (обязательно укажите почему)
[3]00%
 
Всего проголосовали: 14

Оценка стиля изложения

  Все понятно, материал читается легко
[1]1090.9%
 
  Есть неясности в изложении
[2]19.1%
 
  Непонятно написано, трудно читается
[3]00%
 
Всего проголосовали: 11




Смотрите также материалы по темам:
[Задачи оптимизации] [Программирование игр.]

Комментарии жителей
Отслеживать это обсуждение

Всего сообщений: 16

04-01-2011 18:05
Для GEO
Я дал конструктивную критику, но не здесь, а в своей статье на эту тему. Претензия у меня, по большому счету, одна единственная — неэффективная реализация: Вы на каждом шаге пробегаете по всем элементам массива. Это прокатит на относительно небольших массивах, но приведет к жутким тормозам, если размеры массива вырастут.

Это так, но только для случая когда надо кратчайшим путем провести маршрут из одной точки в другую. Ваш варант я читал.
На самом деле, если нужно решать, например, задачу эвакуации множества людей из помещения через некоторый выход, то предварительно рассчитав карту маршрута от выхода во все точки помещения и сохранив ее, вы получите все маршруты всех эвакуируемых, как бы вы их в дальнейшем не расставляли :). А если надо учитывать еще и изменение стоимости прохождения по клеткам от количества занятых соседних (плотность толпы), то такой подход, то что надо для ачала разработки своего решения :)


30-10-2009 13:15
Ой, забыл ответить еще на вот это

>>> В конце концов статью можно изъять
Если статья опубликована, значит она прошла согласование в Команде Королевства. Администрация не возражает против ее размещения, значит, видит в ней полезность. Так зачем же ее изымать? ;-)
 Geo


30-10-2009 13:08
>>> И не видит, к сожалению, конструктивной критики
Увы, раздражающим фактором послужило Ваше присвоение собственного имени давно и хорошо известному (и достаточно простому и очевидному) алгоритму. Поэтому все вертится вокруг этого.

Я дал конструктивную критику, но не здесь, а в своей статье на эту тему. Претензия у меня, по большому счету, одна единственная -- неэффективная реализация: Вы на каждом шаге пробегаете по всем элементам массива. Это прокатит на относительно небольших массивах, но приведет к жутким тормозам, если размеры массива вырастут.

А в целом, все нормально. Вы предложили простую и понятную реализацию для простого случая. Хороший пример для новичков. Если попридираться, то немного подача хромает (или композация): текст программы доминирует, а было бы лучше разбавлять его описанием алгоритма на русском языке. Но в целом, это мелочь. Мы же на программистском форуме, а не на факультете журналистики ;-)
 Geo


30-10-2009 12:47
>>> Geo, помему, вы только и делаете, что иронизируете
Мухтар, а Вы только и делаете, что выказываете недовольство моими действиями?
Вам нужны пояснения по моему предыдущему сообщению, или Вы просто пар выпускали?
 Geo


30-10-2009 08:04
сообщение от автора материала
Спасибо, Мухтар. Да автор сюда заглядывает. И не видит, к сожалению, конструктивной критики. Наверное, не скромно обозвать известный метод своим именем (но как-то же его назвать надо было, хотя бы для идентификации). Ну называйте это
"частным случаем алгоритма Дейкстры"
или "всем известный случай волнового алгоритма" - суть-то не в этом. Я не знал о волновом алгоритме, на олимпиадах по программированию не участвовал и программировать начал сам (без специального образования, если не считать 4-х месячных курсов).
Только не могу понять, что плохого в том, что я описал (на мой взгляд просто и доступно) один из способов решения подобной задачи (пусть и ранее известный).
Да большинство решений описанных в Сокровищнице или в Подземелье Магов на момент их написания были уже кому-то известны. Но тем не менее, я лично благодарен всем авторам , за то что они не поленились и разжевали для меня какую-то задачу, которую, может быть
"любой олимпиадник по программированию"
и так знает.
Кстати, я благодарен так же и Geo, за то что он помогал мне в вопросах на Круглом столе.
Но я не настаиваю на своем мнении. В конце концов статью можно изъять. Но я удовлетворен, что хотя бы двоим (судя по оценкам) моя статья помогла (видимо они тоже не участвовали в олимпиадах по программированию).
 vadi


30-10-2009 06:16
Geo, помему, вы только и делаете, что иронизируете.

Интересно, автор сюда вообще заглядывает?


28-10-2009 11:41
Виктор, Вы бы хоть смайлики ставили что ли. А то, знаете ли, далеко не все посетители в состоянии уловить Вашу тонкую иронию ;-)
 Geo


28-10-2009 09:13
Материал, изложенный в статье обладает наивысшей полезностью, так как предельно элементарным способом  отвечает на базовый вопрос любой задачи - как кратчайшим образом достичь цели, обходя неизбежные препятствия.
Это открытие - один из самых замечательных способов приближения к истине, когда-либо алгоритмизированных, если вообще не единственный.
Внедрение алгоритма Кегелеса-Рауера в другие задачи может
повлечь за собой неожиданные решения, кроме того благодаря этому, теперь становится доступной оптимизация любых процессов, поддающихся дигитализации, что, в конечном счете, означает решение практически любых проблем с минимальными затратами.


07-07-2003 11:49
Genial'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 им тыкают в лицо каждому, кто задает соответсвующий вопрос. В общем, это не новость :)
По большому счету, это частный случай алгоритма Дейкстры.

Ну а реализация, как верно заметил сам автор,-- далека от совершенства.


Добавьте свое cообщение

Вашe имя:  [Войти]
Ваш адрес (e-mail):На Королевстве все адреса защищаются от спам-роботов
контрольный вопрос:
Зимой — белый, летом — серый. Кто?
в качестве ответа на вопрос или загадку следует давать только одно слово в именительном падеже и именно в такой форме, как оно используется в оригинале.
Надоело отвечать на странные вопросы? Зарегистрируйтесь на сайте.

Оценка содержания
 
Содержит полезные и(или) интересные сведения
 
Ничего особенно нового и интересного
 
Написано неверно (обязательно укажите почему)


Оценка стиля изложения
 
Все понятно, материал читается легко
 
Есть неясности в изложении
 
Непонятно написано, трудно читается

Текст:
Жирный шрифт  Наклонный шрифт  Подчеркнутый шрифт  Выравнивание по центру  Список  Заголовок  Разделительная линия  Код  Маленький шрифт  Крупный шрифт  Цитирование блока текста  Строчное цитирование
  • вопрос Круглого стола № XXX

  • вопрос № YYY в тесте № XXX Рыцарской Квинтаны

  • сообщение № YYY в теме № XXX Базарной площади
  • обсуждение темы № YYY Базарной площади
  •  
     Правила оформления сообщений на Королевстве
      
    Время на сайте: GMT минус 5 часов

    Если вы заметили орфографическую ошибку на этой странице, просто выделите ошибку мышью и нажмите Ctrl+Enter.
    Функция может не работать в некоторых версиях броузеров.

    Web hosting for this web site provided by DotNetPark (ASP.NET, SharePoint, MS SQL hosting)  
    Software for IIS, Hyper-V, MS SQL. Tools for Windows server administrators. Server migration utilities  

     
    © При использовании любых материалов «Королевства Delphi» необходимо указывать источник информации. Перепечатка авторских статей возможна только при согласии всех авторов и администрации сайта.
    Все используемые на сайте торговые марки являются собственностью их производителей.

    Яндекс цитирования