Случайный афоризм
То, что по силам читателю, предоставь ему самому. Людвиг Витгенштейн
 
новости
поиск по автору
поиск по тематике
поиск по ключевому слову
проба пера
энциклопедия авторов
словарь терминов
программы
начинающим авторам
ваша помощь
о проекте
Книжный магазин
Главная витрина
Книги компьютерные
Книги по психологии
Книги серии "Для чайников"
Книги по лингвистике
ЧАВо
Разные Статьи
Статьи по литературе

Форма пользователя
Логин:
Пароль:
регистрация
 детектив



 драмма



 животные



 история



 компьютерная документация



 медицина



 научно-популярная



 очередная история



 очерк



 повесть



 политика



 поэзия и лирика



 приключения



 психология



 религия



 студенту



 технические руководства



 фантастика



 философия и мистика



 художественная литература



 энциклопедии, словари



 эротика, любовные романы



в избранноеконтакты

Параметры текста
Шрифт:
Размер шрифта: Высота строки:
Цвет шрифта:
Цвет фона:

  X          x P               X x           P
  X x        l P               X l(x)        P
  X x        r P               X r(x)        P
  X x y z    h P               X h(x,y,z)    P
  X 0        f P               X a           P
  X x        f P               X             x x l f x r f h P

Обозначения: x, y, z,.. - числа, X - последовательность чисел, P
- последовательность чисел и символов "f", "l", "r", "h". В пос-
ледней строке предполагается, что m не равно 0. Эта строка соот-
ветствует равенству

        f(x) = h(x, f(l(x)), f(r(x))),

Эти  преобразования выполняются, пока последовательность не ста-
нет пуста. В этот момент в стеке  окажется  единственное  число,
которое и будет ответом.

     Замечание.  Последовательность по существу представляет со-
бой стек отложенных заданий (вершина которого находится слева).
     Глава 9. Разные алгоритмы на графах

     9.1. Кратчайшие пути

     В этом разделе рассматриваются различные варианты одной за-
дач. Пусть имеется n городов, пронумерованных числами от 1 до n.
Для каждой пары городов с номерами i, j в таблице  a[i][j]  хра-
нится  целое число - цена прямого авиабилета из города i в город
j. Считается, что рейсы существуют между любыми городами, a[i,i]
= 0 при всех i, a[i][j] может отличаться от  a[j,i].  Наименьшей
стоимостью проезда из i в j считается минимально возможная сумма
цен  билетов  для маршрутов (в том числе с пересадками), ведущих
из i в j. (Она не превосходит a[i][j], но может быть меньше.)

     В предлагаемых ниже задачах требуется найти наименьшую сто-
имость проезда для некоторых пар городов при тех или иных  огра-
ничениях на массив a и на время работы алгоритма.

     9.1.1.  Предположим, что не существует замкнутых маршрутов,
для которых сумма цен отрицательна. Доказать, что в этом  случае
маршрут с наименьшей стоимостью существует.

     Решение. Маршрут длиной больше n всегда содержит цикл,  по-
этому минимум можно искать среди маршрутов длиной не более n,  а
их конечное число.

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

     9.1.2. Найти наименьшую стоимость проезда из 1-го города во
все остальные за время O(n в степени 3).

     Решение. Обозначим через МинСт(1,s,к) наименьшую  стоимость
проезда из 1 в s менее чем с k  пересадками.  Тогда  выполняется
такое соотношение:

   МинСт (1,s,k+1) = наименьшему из чисел МинСт(1,s,k) и
                     МинСт(1,i,k) + a[i][s] (i=1..n)

Как отмечалось выше, искомым ответом является  МинСт(1,i,n)  для

1 : 2 : 3 : 4 : 5 : 6 : 7 : 8 : 9 : 10 : 11 : 12 : 13 : 14 : 15 : 16 : 17 : 18 : 19 : 20 : 21 : 22 : 23 : 24 : 25 : 26 : 27 : 28 : 29 : 30 : 31 : 32 : 33 : 34 : 35 : 36 : 37 : 38 : 39 : 40 : 41 : 42 : 43 : 44 : 45 : 46 : 47 : 48 : 49 : 50 : 51 : 52 : 53 : 54 : 55 : 56 : 57 : 58 : 59 : 60 : 61 : 62 : 63 : 64 : 65 : 66 : 67 : 68 : 69 : 70 : 71 : 72 : 73 : 74 : 75 : 76 : 77 : 78 : 79 : 80 : 81 : 82 : 83 : 84 : 85 : 86 : 87 : 88 : 89 : 90 : 91 : 92 : 93 : 94 : 95 : 96 : 97 : 98 : 99 : 100 : 101 : 102 : 103 : 104 : 105 : 106 : 107 : 108 : 109 : 110 : 111 : 112 : 113 : 114 : 115 : 116 : 117 : 118 : 119 : 120 : 121 : 122 : 123 : 124 : 125 : 126 : 127 : 128 : 129 : 130 : 131 : 132 : 133 : 134 : 135 : 136 : 137 : 138 : 139 : 140 : 141 : 142 : 143 : 144 : 145 : 146 : 147 : 148 : 149 : 150 : 151 : 152 : 153 : 154 : 155 : 156 : 157 : 158 : 159 : 160 : 161 : 162 : 163 : 164 : 165 : 166 : 167 : 168 : 169 : 170 : 171 : 172 : 173 : 174 : 175 : 176 : 177 : 178 : 179 : 180 : 181 : 182 : 183 : 184 : 185 : 186 : 187 : 188 : 189 : 190 : 191 : 192 : 193 : 194 : 195 : 196 : 197 : 198 : 199 : 200 : 201 : 202 : 203 : 204 : 205 : 206 : 207 : 208 : 209 : 210 : 211 : 212 : 213 : 214 : 215 : 216 : 217 : 218 : 219 : 220 : 221 : 222 : 223 : 224 : 225 : 226 : 227 : 228 : 229 : 230 : 231 : 232 : 233 : 234 : 235 : 236 : 237 : 238 : 239 : 240 : 241 : 242 : 243 : 244 : 245 : 246 : 247 : 248 : 249 : 250 : 251 : 252 : 253 : 254 : 255 : 256 : 257 : 258 : 259 : 260 : 261 : 262 : 263 : 264 : 265 : 266 : 267 : 268 : 269 : 270 : 271 : 272 : 273 : 274 : 275 : 276 : 277 : 278 : 279 : 280 : 281 : 282 : 283 : 284 : 285 : 286 : 287 : 288 : 289 : 290 : 291 : 292 : 293 : 294 : 295 : 296 : 297 : 298 : 299 : 300 : 301 : 302 : 303 : 304 : 305 : 306 : 307 : 308 : 309 : 310 : 311 : 312 : 313 : 314 : 315 : 316 : 317 : 318 : 319 : 320 : 321 : 322 : 323 : 324 : 325 : 326 : 327 : 328 : 329 : 330 : 331 : 332 : 333 : 334 : 335 : 336 : 337 : 338 : 339 : 340 : 341 : 342 : 343 : 344 : 345 : 346 : 347 : 348 : 349 : 350 : 351 : 352 : 353 : 354 : 355 : 356 : 357 : 358 : 359 : 360 : 361 : 362 : 363 : 364 : 365 : 366 : 367 : 368 : 369 : 370 : 371 : 372 : 373 : 374 : 375 : 376 : 377 : 378 : 379 : 380 : 381 : 382 : 383 : 384 : 385 : 386 : 387 : 388 : 389 : 390 : 391 : 392 : 393 : 394 : 395 : 396 : 397 : 398 : 399 : 400 : 401 : 402 : 403 : 404 : 405 : 406 : 407 : 408 : 409 : 410 : 411 : 412 : 413 : 414 : 415 : 416 : 417 : 418 : 419 : 420 : 421 : 422 : 423 : 424 : 425 :
главная наверх

(c) 2008 Большая Одесская Библиотека.