What is the main difference between IDA* and IDDFS? via /r/learnprogramming


What is the main difference between IDA* and IDDFS?

I was thinking about this today because a friend of mine wrote a program that does a similar task that I do as well but using different algorithms. I decided to use IDDFS and he used IDA. We both prune our searches in similar ways but I was wondering if the way I prune my IDDFS search makes it an IDA.

I have an object that gets manipulated that can get manipulated 18 different ways. I use my IDDFS search to reach the each position in BFS order. At each depth of the search I try each of the 18 different ways the object can be manipulated each depth allows the number of manipulations to be as long as depth.( Example if depth in the search is 4 the amount of manipulations to that object 4. AKA sequence length). Now that I have explained that I have a pruning table which has sequence lengths in it. Each index in the prune table maps to a position in the object that already has been found. I do this to prune the search. Let SL = sequence length, D = depth, T = target depth.

if(SL + D > T) return

This saves time drastically. I thought that having this "cost", the sequence length of the object, D and the one in the prune table SL, that allows that current iteration to return would make my algorithm an IDA* algorithm. Would this mean my IDDFS algorithm effectively a IDA* because I prune the search based on cost to get from one state to another?

Sorry if my explanation isn't clear enough if you have any questions feel free to ask I will try to clear it up.

Submitted July 16, 2017 at 05:40PM by FlippngProgrammer
via reddit http://ift.tt/2vs8d4c

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s