Для обеспечения корректной работы программы «Программа планирования туристической поездки по городам России» необходимо провести испытание программного продукта, который включает следующие этапы:
- создание совокупности тестовых эталонных значений и правил, которым должна соответствовать программа по выполняемым функциям, структуре, правилам описания значений входных данных;
- диагностика и локализация причин отклонения результатов тестирования от заданных эталонных значений;
- изменение программы с целью исключения причин отклонения результатов тестирования от эталонных значений;
- реализация корректировки программы, обеспечивающая соответствие программного продукта заданному эталону.
Программа «Программа планирования туристической поездки по городам России» должна соответствовать всем требованиям технического задания.
Тестовый пример
Генерируем матрицу (полный граф). Отображаем граф на экране. Коммивояжеры ходят по графу. Их надо отображать. Когда коммивояжер стоит на развилке он с большей вероятностью уйдет по более протоптанной дорожке. Проходя по дорожке коммивояжер протаптывает дорожку. Чем больше вес дуги тем дольше коммивояжер идет по дорожке. Пройдя по всем городам коммивояжер возвращается той же дорогой, по которой обошел все города.
При запуске приложения происходит построение(генерация) полного графа (по умолчанию, количество вершин в начальном графе = 7). После того, как граф построен, граф отображается на экране. В этот же момент параллельно (на фоне) запускается альтернативное жадное решение, которое уведомляет приложение (главную форму) о своем результате с помощью события. Результат альтернативного жадного решения отображается на экране.
Примечание: изначально граф содержит только вершины, так как никто из коммивояжеров дорожки еще не протоптал. При изменении количества вершин, граф перестраивается в режиме онлайн.
Далее, при нажатии на кнопку "Новый коммивояжер", появляется новый коммивояжер в случайной вершине. При движении коммивояжер окрашивается в цвет вершины, к которой он в данный момент двигается. Выбор очередной "цели" - вершины, к которой необходимо осуществить движение - происходит в соответствии с формулировкой задачи, а именно: по достижении текущей "цели", коммивояжер с большей вероятностью (в данной реализации используется линейная зависимость) пойдет по более протоптанной дорожке. Посетив все вершины, коммивояжер возвращается той же дорогой, по которой обошел все вершины. По возвращению в стартовую вершину, коммивояжер сообщает о своем пройденном пути приложению (главной форме) с помощью события и завершает свою жизнь. В случае необходимости происходит обновление и отображение текущего оптимального пути.
Некоторые технические особенности реализации:
1. Использован объектно-ориентированных подход - все элементы задачи (характеристики и поведение) описываются собственным классом. Пример:
public class Дуга
{
public Вершина вершина1;
public Вершина вершина2;
public int вес;
public int количество_прошедших;
public Дуга(Вершина _вершина1, Вершина _вершина2, int _вес) {
вершина1 = _вершина1;
вершина2 = _вершина2;
вес = _вес;
количество_прошедших = 0;
}
}
2. Структура поведения Коммивояжера (живет в отдельном потоке):
public class Коммивояжер
{
void Сделать_шаг();
Вершина Получить_новую_цель();
void Жизнь_коммивояжера() {
while (необходимо_продолжить_путь) {
if (текущая_цель_достигнута)
цель = Получить_новую_цель();
Сделать_шаг();
}
if (я_вернулся_событие!= null)
я_вернулся_событие(this);
}
}
3. Структура Жадного_вычислителя (вычислитель и каждый помощник живут в отдельных потоках):
public class Вычислитель_жадный
{
public class MyComparer: IComparer<Дуга> {}
public class Помощник_вычислителя {
void Вычислить_из_вершины() {}
}
List<Помощник_вычислителя> список_помощников;
void Жизнь_вычислителя_жадного() {
список_помощников = new List<Помощник_вычислителя>();
foreach (var вершина in список_вершин) {
Помощник_вычислителя текущий_помощник = new Помощник_вычислителя(вершина, граф, список_вершин);
список_помощников.Add(текущий_помощник);
текущий_помощник.поток.Start();
}
foreach (var помощник in список_помощников) {
помощник.поток.Join();
if (помощник.вес_пути < вес_пути) {
путь = помощник.мой_путь;
вес_пути = помощник.вес_пути;
}
}
if (я_вычислил!= null) я_вычислил(this);
}
}
4. Отрисовка реализована по таймеру
5. Работа с журналом (ведение лога в файл) реализовано с помощью статического класса.