Horses and the Grey's Scouts
The Afghanis (at least some of them) have a great tradition of horsemanship.
Saw the book Horse Soldiers where the first US SF in Afghanistan in 2001 made use of horses during their mission. Probably because there was no other mobility available.
Rhodesia had the Grey's Scouts, a mounted infantry rather than a cavalry unit who had a tracking ability and also were working on the use of dogs (coonhounds) running free in this regard. Lacking tracking devices and GPS transmitters in those days there was always the real potential to lose the dogs or get separated. The trials were never fully completed by the end of the war.
There were a number of occasions where Grey's were able to cover tremendous distances at a steady canter on obvious spoor. This would be where they came across spoor of large groups of heavily laden insurgents following a well warn path/route or in a post contact situation where the insurgents were fleeing with no time to anti/counter track. The dogs would have been better where anti-counter tracking was being used.
The Rhodesian Air Force also carried out some trials using free running dogs as recorded in the excellent work Winds of Destruction by Peter Petter-Bowyer
Tracker dogs proven
Final Tracker Dog Trial
In our small overstretched military we did not have the time to work on the concept of free running dogs for tracking purposes. Maybe others elsewhere have had more experience with dogs and/or mounted infantry tracking.