Backtracking (Think Like a Programmer)
ฝัง
- เผยแพร่เมื่อ 15 ม.ค. 2018
- Backtracking is used when you need to find the correct series of choices that will solve a problem. The example I use here is finding one's way through a maze. You can use the basic idea with or without recursion; if you haven't seen my other videos on recursion, start with the first one at • Recursion (Think Like ...
This topic was a viewer suggestion--your suggestions for future videos are welcome.
If you want to read more about my programming concepts, check out my "Think Like a Programmer" book. If you've found that you are able to read programs and understand programming language syntax but aren't always confident writing programs from scratch, my book can help.
For more information on the book head to one of these:
Amazon page for the book: amzn.to/1MZlmlY
My site: www.vantonspraul.com/TLAP
My publisher's site: nostarch.com/thinklikeaprogrammer
Connect with me:
My site: vantonspraul.com
Twitter: / vantonspraul
Facebook: / thinklikeaprog - วิทยาศาสตร์และเทคโนโลยี
"Don't even think about the recursion that's happening. Just imagine you are calling a different, working function" - Best explanation ever. This line lit the lightbulb in my head. Thanks :)
dude - this was the video that actually unlocked the concept of backtracking for me, in a way that I can now start to understand problems going forward. Huge props. I will have to check out your library of videos and i'm not sure if you're still making them but if so I'd love to hear you explain some more concepts. Thanks for making the effort, its much appreciated
This was amazing, thank you for also not jumping into recursion but instead showing this solution.
I was looking for videos on backtracking.. i did not want to waste my time.. so i scrolled many times before i found a video title that talked about "thinking" about backtracking.. well done sir!!
Thank you so much for creating this video - you explained recursive backtracking in a very easy to understand way, as well as showing the relevant code!
"Not think about the backtracking" - this literally changed my life :D So good!
this is one of the best explanations I've ever seen. I wish you to keep going on to brush up more information
You are amazing. You really made backtracking very simple.
that Robot analogy was amazing!
Thanks for the video
I haven't finished the video but right now, I keep thinking about all of the different paths that you can go down, keep thinking about the recursion... and then once you return you go up the path until you can make another decision based off of where you end up but it's just very... complex when you think about it... I mean the base cases do make a lot of sense but the way I'm thinking about it right now is too hard to grasp, it's almost mind bending.
Thank you very much!! i dont know why you content underrated. keep making videos good luck!
Thank you so much! I've learned new things from you.
This is one of the best explanations I've ever found. Thanks for making this video :)
Thanks for your comment. Glad you found it useful.
Best backtracking video I found on youtube.
Thanks man! Very well explained! Keep going!
Very nice explanation! I love it.
Can you explain 8 queens problem. I found your explanation and reasoning very clear.
Thank you, great video, iterative solution was very intuitive
This explanation is awesome!
Thank you for this amazing explanation
This channel should create more content. I'm learning a lot.
Thank you sir for this wonderful series of videos ...
You're welcome! More on the way.
Splendid explanation!
Amazing explanation. Really helped, thanks so much.
Really nice explanation! :D
wow! just wow! thank you sir!
Great explanation
really inspiring. I always got confused when I tried to think about backtracking in recursions, now I don't.
Nice vid! What microphone are you using?
You should be a teacher. The way you lay out your thought process in a simple and detailed manner, allows us to replicate that thought process on our own and gain a deep understanding.
He is a teacher :))
Yeah, or he could make videos teaching. In a youtube channel or something like that.
He is a teacher, and one of the best I’ve had
Was sent here by Sweigart's recursion book!
I need some serious help. I can understand how this works but I cant come up with a code by myself.
it's such an excellent work!
somtimes programmer kinda like MATH! OH WAIT !
Best way to understand ...thanks
Thanks! Glad it was helpful.
Really great video, thanks for giving a non-recursive solution, it helps putting things back in perspective.
I'm wondering if this can apply to problems that search for a min/max value? For example, the classic "bag" problem which is traditionally solved using more "combinatory-oriented" approaches. (bag can carry at most N kilos and you have many items worth different values and weights, and you want to find the combination of a minimum items that are worth the maximum amount of gold)
Thanks! Yes, you could use recursion to solve that problem, which I know as the knapsack problem. The function could have two parameters: a maximum weight (maxWeight), and a list or other structure with all the items (AllItems), each with a weight and value. Also suppose there is an easy way to make a copy of that list without its first item (AllButFirst). The logic would then be, which of these has greater value?
A. the recursive call with (maxWeight, AllButFirst)
B. the recursive call with (maxWeight - weight of first item in AllItems, AllButFirst) + value of the first item in AllItems
The recursion would stop when AllItems has zero items. Something like that.
great video!
Fantastic!
thnank you so much the vedio was intersting i would like to use this algorithm to maximize a funtion how can i? thank you in advance
video very easy understand.thanks!
Glad you liked it!
Hope everyone is having a great 2018 so far. This video's topic was viewer suggested. If you have an idea for a future video, let me know!
Dijkstra and belmanford shortest algorithm ...Can u explain us.practically
...
Sure, that sounds like a good topic. I'll add it to the list. Thanks for the suggestion!
sir video tutorials are common nowadays but ur videos are unique because u r speaking about how to approach the problem rather than giving a question and solvng it so do more of such videos on how to approach the problem in a different manner
Well done on the video!
Can you do it for python please
Good idea!
i have a question. how could u make the while loop with conditions iter and foundoutlet terminates because i didn't see anything to trigger its termination here?
Nice video!
Amazing 💗
Helpful!
Could you show how the list sample_maze is being generated and called in main?
When I called the backtrack function sample_maze[9] is empty.
Nice video. May I also add that he sounds a lot like Kevin Spacey from House of cards...
can u give me the link of the code that u showed in video?
Thanks for the useful example of coding with Stacks.
You are welcome. Thanks for checking it out.
Does the code without recursion actually works?? I've tried to replicate it in ruby but I have found some roadblocks. Probably due to the use of List here... How exactly do the begin() and end() methods work?
The code all works. I've done very little programming in Ruby, so I can't help you there. But I can explain how a list iterator works. Let me start by analogy and see if this helps. Imagine that we declared an array myArray and the constant SIZE specified how many members were in the array. So myArray[0] through myArray[SIZE - 1]. Then begin() would be like setting a variable called arrayPosition to 0, the first index of an array. And end() would give you SIZE, so if arrayPosition == SIZE it means you have advanced arrayPosition off the end of the array. (I think in Ruby you can legally reference elements outside the original range of the array, but you get the idea). Because you can dynamically add elements to arrays in Ruby I think the code should be translatable from C++ lists to Ruby arrays. Let me know if you have any more specific problems and I'll try to help.
quality content
Amazing pls more
Can you please do these in java too?
very cool
recursion is so counter-intuitive!
Best explanation 😎
Thank you! I'm glad you liked it.
If you want to know what is happening with recursive backtracking each possible route (assuming the maze is solvable) is made out after each step you take. The program knows all the results before it actually prints back anything to you! Like a teacher grading a paper, you don't know the grade until they tell you. If you step into a wall the code says welp I am done time to free up some memory and undos the step that led you to the wall. Why? Because programming languages keep track of things (like each step in a maze) using a stack of method calls. Once you walk into the brick wall in the maze the program says okay nothing to do here lets pop off all our steps. Oh wait now I can go this way (0-3)
Obviously just imagining you are calling a different, working function is a much simpler way to think about it.😅
I have a question... how do you use backtracking in finding all possible permutations of arranging n items?
That's the kind of problem where "backtracking" would be implicit and hard to see as such. Let's say you wanted to produce all the permutations of the letters A through Z. Let's suppose the language you are working in has a string library with functions or methods that 1) add a character to the end of a string 2) determine the length of a string 3) gets you the character at a certain position and 4) tells you if a character is in a string.
Then we could write a recursive function to output all permutations of A through Z as follows. Our function has one parameter called PartialPermute. The code in the function would do this:
-- if PartialPermute has 26 characters, output it and end the function (i.e., return)
-- otherwise, loop a variable called Letter from 'A' to 'Z'
---- inside the loop, check to see if Letter is not already in the string PartialPermute
------- if not, copy PartialPermute to TempString, append Letter to TempString, and recursively call this function, passing TempString as the argument
That's pretty much it. Again, backtracking here is implicit. You could make the backtracking more visible by appending Letter directly to PartialPermutre instead of using TempString, and then you would have to strip the last latter off PartialPermute after the recursive call, a kind of backtracking.
Of course, if you wanted to store the results instead of display them or make a more general permutation function this would have to be expanded a bit but that's the basic idea.
Thank you! I have researched a little bit on the subject and your video was the best explanation of even an indirect example of the problem I had. Well done!
What is this typeface? It's very pleasing
Looks like Consolas to me :)
Sorry for the delay. It's Futura-Book.
#cons : Type your program while you're explaining otherwise it will be difficult to go through. Explain the concept before hand.
Thanks for your Video👍
I have a doubt,this library that includes "push_back", "empty", "insert", how can i implement in C?
(don't get angry please, i'm still learning, but in C, not C++)
you need to do by your self. They are not included in standard c libraries.
Nicolas Wolyniec thanks
Whats the difference between this and DFS?
DFS is an implementation of backtracking for graphs.
Didn't understand how the recursive part worked
this is great but i wish you could explain the same thing on python :(
would be nice if you used a dark or black background too
The maze problem is basically solved by depth-first search.
Nice, but it video is lacking graphical input on what is happening in each step of the backtracking
widce
define
where can we get the source code?
Dude, In the 1st solution you have used the (!) operator with foundOutlet(line 26) which is declared false. Your program will never enter the second loop.
Remove (!) then the program will work just fine.
In the first program when I'm printing iter at line 25 and line 27(say) i.e before and after the second while loop its giving me {1,0,1,0,1,0,3,4,3,4} and {1,0,2,1,0,2,1,3,0,4,3,5,4,3,5,7,4,8} respectively. Im unable to understand how the iterator is moving.
um no that is wrong, the loop will execute as foundOutlet is set to false, and the second while loop only executes if this boolean value is set to false. if foundOut was set to true then the loop would not execute
Dear TH-cam Algorithm, please give me more of these practical SWE videos and less tech influencer garbage
Oh, if only we could talk directly to the algorithm...anyway, glad you found it helpful.
*Applause*
An even better approach is just to make all the right decisions the first time around. Then you never have to backtrack.
Ha! For that you'll need a non-deterministic computer. You still don't make only right decisions, but because you make all possible decisions simultaneously, you can pick the one that ends up at the exit.
U sound like khan academy!
Could you program when you teach instead of talking about the code which has been done?
everyone saying amzing amazing just answer one question why (!foundOutlet) is written in while loop ?
I can try to answer that. Do you mean literally why it's part of the while loop condition? That loop exists to set foundOutlet to true if we find a connection from the current point to an unvisited point. We're not counting how many unvisited points we can reach, we only need to know if we can reach one, or not. So once we find an unvisited point (setting foundOutlet to true), we don't need to continue the loop further. That's why the !foundOutlet condition. Of course there would other ways of accomplishing the same thing. Let me know if this isn't what you meant.