Алгоритм бектрекінг. Звіт до лабораторної роботи з Методи і системи штучного інтелекту. Робота № 530968

Алгоритм бектрекінг

Інформація про навчальний заклад

ВУЗ:

Національний університет Львівська політехніка

Інститут:

Не вказано

Факультет:

КН

Кафедра:

Не вказано

Інформація про роботу

Рік:

2019

Тип роботи:

Звіт до лабораторної роботи

Предмет:

Методи і системи штучного інтелекту

Завантажити

Частина тексту файла (без зображень, графіків і формул):

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІСЬКА ПОЛІТЕХНІКА» Кафедра ІСМ Звіт До лабораторної роботи №4 З дисципліни: «Методи та системи штучного інтелекту» На тему: «Алгоритм бектрекінг» Львів-2017 Мета роботи: полягає у вивченні алгоритмів бектрекінг та його застосування при розв’язуванні задач штучного інтелекту. Теоретичні відомості Опишемо загальний метод, який дозволяє значно зменшити об’єм обчислень в алгоритмах типу „повного перебору всіх можливостей”. Щоб застосувати цей метод, розв’язок задачі повинен мати вигляд послідовності (x x) n , ..., 1 . Основна ідея методу полягає в тому, що розв’язок будується поступово, починаючи з порожньої послідовності (довжини 0), або з одноелементної послідовності (довжини 1). Взагалі, якщо маємо даний частковий (неповний) розв’язок ( ) i x , , x 1.. , де i<n , то намагаємось знайти таке допустиме значення i+1 x , що не включається можливість продовження ( ) 1 1 , , , i i x x x ( ) до повного розв’язку. Якщо такого значення i+1 x не існує, то повертаємось до попередньої послідовності ( ) 1 1 , I x x і продовжуємо процес, шукаючи нове, ще не використане значення xi ( ) звідси назва „бектрекінг” (англ. backtracking – пошук з поверненням). Роботу цього алгоритму можна інтерпретувати як процес обходу деякого дерева. Кожна вершина цього дерева природно відповідає деякій послідовності ( ) i x , , x 1, причому вершини, які відповідають послідовностям виду (x x y) i , , , 1 .. , є синами цієї вершини. Корінь дерева відповідає порожній, а в деяких задачах одноелементній послідовності. В алгоритмі бектрекінг здійснюється обхід цього дерева пошуком вглиб (для дерева це означає обхід зверху вниз). Крім того, задається предикат P , означений на всіх вершинах дерева. У випадку P (v) =F процес обходу відкидає розгляд вершин піддерева з коренем у вершині v , зменшуючи тим самим обсяг перебору. Завдання лабораторної роботи: Знайти підмножину цієї множини таку, що сума її елементів дорівнює даному числу M ( k =1). Результати виконання роботи: package PHSHI.Lab4; import java.util.ArrayList; import java.util.Scanner; public class Lab4 { public static void main(String[] args) { System.out.println("Введіть кількість елементів множини:"); Scanner scanner = new Scanner(System.in); int count = scanner.nextInt(); System.out.println("Введіть " + count + " елементів множини"); int matrix[] = new int[count]; for (int i = 0; i < count; i++) { matrix[i] = scanner.nextInt(); } ArrayList<Integer> list = new ArrayList<Integer>(); ArrayList<String> list2 = new ArrayList<String>(); list2.add("a"); System.out.println("Введіть М:"); int M = scanner.nextInt(); int sum = 0, count2 = 0; int f = fact(count); int i = 0; int count3 = 0; m1: while (sum != M && count2 < f) { if (i < count) { if (!list.contains(matrix[i])) if (!contain(list2, list.toString())) { sum += matrix[i]; if (sum == M) { list.add(matrix[i]); break m1; } if (sum < M) { list.add(matrix[i]); i++; count3 = i; } else { sum -= matrix[i]; count3++; i++; } if (count3 >= count && list.size() > 0) { // System.out.println(list.toString()); list2.add(list.toString()); sum -= list.get(list.size() - 1); list.remove(list.size() - 1); i = 0; count3 = 0; } } else { sum -= matrix[--i]; if (list.size() > 0) list.remove(list.indexOf(matrix[i])); i++; count3 = list.size(); // System.out.println("List: "+list); } else i++; } else if (i > 1) i = 0; count2++; System.out.println(list + " " + sum); } System.out.println("Winner: " + list); } static int fact(int count) { if (count == 1) return 1; else return fact(count - 1) * count; } static boolean contain(ArrayList<String> list2, String list) { for (int i = 0; i < list2.size(); i++) if (list2.get(i).equals(list)) { // System.out.println(list2.get(i) + " " + list); return true; } return false; } } В даній програмі використовувався текстовий інтерфейс. Нам спершу необхідно ввести деякі елементи множини, щоб надалі виконати умови поставленого завдання. /Рис. 1. Результати виконання роботи Висновок Виконавши дану лабораторну роботу, вивчила алгоритми бектрекінгу та його застосування при розв’язуванні задач штучного інтелекту.

Звіт до лабораторної роботи Методи і системи штучного інтелекту

Roksolana64

30.05.2019 15:59

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

поділитись