Код PHP. Решение Задачи Коммивояжера методом ближайшего соседа

Министерство образования Республики Беларусь

 

Учреждение образования

Международный государственный экологический институт

им. А. Д. Сахарова БГУ

 

 

Факультет мониторинга окружающей среды

 

 

Кафедра экологических информационных систем

 

 

КОНТРОЛЬНАЯ РАБОТА №1

 

по дисциплине «Программирование сетевых приложений»

 

Студентки 4-го курса группы 33011

 

ЧаладзеНиноБесиковны

 

 

Номер зачетной книжки 33011-07

 

 

Минск 2017


 

Разработка сайта.

 

Перед установкой Joomla на сервер хостинга (https://www.000webhost.com), скачаем дистрибутивы. С сайта joomla.ru качаем последнюю версию Joomla, скачиваем также пакет русской локализации.

Зарегистрируем доменное имя своего сайта на бесплатном хостинге. Распакованный дистрибутив CMS и грузим на сервер хостинга.

После загрузки на сервер хостинга, в корневую директорию всех файлов и папок распакованного предварительно дистрибутива Joomla, вводим в адресной строке браузера его доменное имя.

На странице, которая открылась,введем название и описание сайта ((http://nino.site50.net).

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

Создадим базу данных и пользователя с паролем.

После удаления директории 'Installation' войдем в админку. Вводим http://nino.site50.net/administrator. Вводим Логин и пароль, выбираем язык и входим в административную панель Joomla.

Приступаем к разработке сайта (http://nino.site50.net) Наполняем контент сайта необходимой информацией.

Страницы сайта:

Главная

Об управлении

 

Одно окно

Задача Коммивояжера код на Php.

Перед тем как вставить Php код на наш сайт не обходимо скачать плагин Sourcerer с сайта (https://extensions.joomla.org/extension/sourcerer/) и установить его на Joomla. После того как мы его установим материалах появится кнопка

Нажимаем на кнопку «<>Код» и вставляем  туда код.

Код содержится в административной панели Joomla->Материалы-> Менеджер материалов->

Алгоритм ближайшего соседа — один из простейших эвристических методов решения задачи коммивояжёра. Относится к категории «жадных» алгоритмов.

Формулируется следующим образом:

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

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

Для любого количества городов, большего трех, в задаче коммивояжёра можно подобрать такое расположение городов (значение расстояний между вершинами графа и указание начальной вершины), что алгоритм ближайшего соседа будет выдавать наихудшее решение.


Код PHP. Решение Задачи Коммивояжера методом ближайшего соседа

{source}

<?php

// добавление стилей в блок <head>

 

$css = "

table input {

           box-sizing: border-box;

           width: 100%;

 

           }

.item-page {font-style: italic!important;}

form[name=cities_distance] input[readonly] {

background-color: #F8E0EC; //цветзеркальныхячеек

color: #000!important;

font-style: italic!important;

}

form[name=cities_distance] .readonly {

background-color: #F5A9D0!important; //цветячеекподиагонали

}

form[name=cities_distance] input {

padding: 16px!important;

font-style: italic!important;

}

";

$doc->addStyleDeclaration($css);

echo "[[h2]]Методближайшегососеда[[/h2]]";

echo '[[labelfor="cities"]]Введите количество городов[[/label]]';

$cities = 2;//количество городов по умолчанию (2)

if (isset($_GET['cities'])) { //ввод значения количества городов, если оно не изменяется, то остается по умолчанию

$cities = $_GET['cities'];// отображение параметров в адресной строке

}

//форма для ввода количества городов

 

echo '[[formmethod="GET" name="cities_count"]]//количество городов в адресной строке

[[input type="number" name="cities" id="cities" value="' . $cities . '" min="2" ]]

   [[button type="submit"]]Принять[[/button]]

[[/form]][[br]]';

 

echo '[[formmethod="POST" name="cities_distance"]] //параметры которые не отражаются в адресной строке

[[table]]';//создается матрица, заполняющаяся зеркально, по строчно

for ($i = 0; $i < $cities; $i++) {//строки

echo '[[tr]]';

for ($j = 0; $j < $cities; $j++) {//столбцы

   echo '[[td]]';

   if ($i > $j) {

       $_POST['i'][$i][$j] = $_POST['i'][$j][$i];

echo '[[input type="text" name="i[' . $i . '][' . $j . ']" readonlytabindex="-1" class="readonly2" value="' . ($_POST['i'][$i][$j] ?: '0') . '"]]';

   } elseif ($i == $j) {

echo '[[input type="text" name="i[' . $i . '][' . $j . ']" readonlytabindex="-1" class="readonly" value=""]]';

   } else {

echo '[[input type="text" name="i[' . $i . '][' . $j . ']" value="' . ($_POST['i'][$i][$j] ?: '0') . '" ]]';

   }

   echo '[[/td]]';

}

echo '[[/tr]]';

}

echo '[[/table]]';

echo '[[button type="submit"]]Посчитать[[/button]]';

echo '[[/form]]';//заполнение данных в верхнем угле матрицы

if ($_SERVER['REQUEST_METHOD'] == 'POST') {

$sum = array();

for ($from = 0; $from < $cities; $from++) {

   $sum[$from] = 0;

   $distances = $_POST['i'];

 

   $at = $from;

   $route = array();

   $route[] = $from;

 

   while ($distance = $distances[$at]) {//исключаетповторения

foreach ($routeas $r) {//алгоритм выбора ближайшего города

unset($distance[$r]);

       }

       if (empty($distance)) {

           break;

       }

       $min = array_keys($distance, min($distance))[0];

       $route[] = $min;

       $at = $min;

   }

$route[] = $from;

 

echo '[[h3]]Цепочка городов из города [[b]]' . $from . '[[/b]][[/h3]][[p]]';

   for ($i = 0; $i < count($route) - 1; $i++) {

       $sum[$from] += $_POST['i'][$route[$i]][$route[$i + 1]];

echo '[[b]]' . $route[$i] . '[[/b]] - [[i]]' . $_POST['i'][$route[$i]][$route[$i + 1]] . '[[/i]] - ';

   }

echo '[[b]]' . $route[count($route) - 1] . '[[/b]][[/p]][[p]]Общее расстояние: ' . $sum[$from] . '[[/p]]';

}

           $mins = array_keys($sum, min($sum));

           echo '[[p]]Минимальное расстояние из города(-ов): ' . implode(', ', $mins) . '[[/p]]';

}

?>

{/source}

Вот как выглядит последняя страница нашего сайта.


Блок-схема


Дата добавления: 2018-05-12; просмотров: 598; Мы поможем в написании вашей работы!

Поделиться с друзьями:




Мы поможем в написании ваших работ!