Обсуждение:Обход в ширину — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(вопросы по правке статьи)
 
(Последние замечание: Новая тема)
 
Строка 6: Строка 6:
  
 
--[[Участник:Sementry|Мейнстер Д.]] 05:48, 17 ноября 2011 (MSK)
 
--[[Участник:Sementry|Мейнстер Д.]] 05:48, 17 ноября 2011 (MSK)
 +
 +
== Последние замечание ==
 +
 +
1) Употребление слова оптимальный, не говорит о том, в каком смысле оптимальный.
 +
2) d[u] != p[s,u]

Текущая версия на 04:51, 18 ноября 2011

К последним замечаниям:

  • Оставшиеся "Оптимальные расстояния/пути" заменить на "длины кратчайших путей"
Заменил, но не понимаю, чем плохо слово "оптимальный"? Там, где имелся в виду сам путь, а не его длина, оставил что-то вроде "кратчайший путь".
  • В теореме о корректности не ясно, почему до w расстояние найдено верно, ведь из того, что w - предок u в кратчайшем пути не следует, что d[w] < d[u]
По-моему, это очевидно. Пусть [math] s{w_1}{w_2}{\ldots}wu [/math] - этот кратчайший путь. Понятно, что [math] s{w_1}{w_2}{\ldots}w [/math] - кратчайший путь до [math] w [/math] (если бы он был не кратчайшим, то можно было бы заменить его на кратчайший в пути до [math] u [/math], значит, путь до [math] u [/math] тоже не кратчайший). Мы рассматриваем невзвешенный граф, поэтому вес каждого ребра равен 1. Значит, [math] d[u] = d[w] + 1 [/math]. Если нужно, могу добавить эти соображения в статью, если я неправ, то объясните, пожалуйста, в чем именно.

--Мейнстер Д. 05:48, 17 ноября 2011 (MSK)

Последние замечание

1) Употребление слова оптимальный, не говорит о том, в каком смысле оптимальный. 2) d[u] != p[s,u]